DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2024.65

FPT Approximation for Capacitated Sum of Radii

Authors: Ragesh Jaiswal, Amit Kumar, and Jatin Yadav

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract

We consider the capacitated clustering problem in general metric spaces where the goal is to identify k clusters and minimize the sum of the radii of the clusters (we call this the Capacitated k-sumRadii problem). We are interested in fixed-parameter tractable (FPT) approximation algorithms where the running time is of the form f(k) ⋅ poly(n), where f(k) can be an exponential function of k and n is the number of points in the input. In the uniform capacity case, Bandyapadhyay et al. recently gave a 4-approximation algorithm for this problem. Our first result improves this to an FPT 3-approximation and extends to a constant factor approximation for any L_p norm of the cluster radii. In the general capacities version, Bandyapadhyay et al. gave an FPT 15-approximation algorithm. We extend their framework to give an FPT (4 + √13)-approximation algorithm for this problem. Our framework relies on a novel idea of identifying approximations to optimal clusters by carefully pruning points from an initial candidate set of points. This is in contrast to prior results that rely on guessing suitable points and building balls of appropriate radii around them. On the hardness front, we show that assuming the Exponential Time Hypothesis, there is a constant c > 1 such that any c-approximation algorithm for the non-uniform capacity version of this problem requires running time 2^Ω(k/polylog(k)).

Cite as

Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. FPT Approximation for Capacitated Sum of Radii. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 65:1-65:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jaiswal_et_al:LIPIcs.ITCS.2024.65,
  author =	{Jaiswal, Ragesh and Kumar, Amit and Yadav, Jatin},
  title =	{{FPT Approximation for Capacitated Sum of Radii}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{65:1--65:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.65},
  URN =		{urn:nbn:de:0030-drops-195937},
  doi =		{10.4230/LIPIcs.ITCS.2024.65},
  annote =	{Keywords: Approximation algorithm, parameterized algorithm, clustering}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2023.7

An Optimal Algorithm for Sorting in Trees

Authors: Jishnu Roychoudhury and Jatin Yadav

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract

Sorting is a foundational problem in computer science that is typically employed on sequences or total orders. More recently, a more general form of sorting on partially ordered sets (or posets), where some pairs of elements are incomparable, has been studied. General poset sorting algorithms have a lower-bound query complexity of Ω(wn + n log n), where w is the width of the poset. We consider the problem of sorting in trees, a particular case of partial orders. This problem is equivalent to the problem of reconstructing a rooted directed tree from path queries. We parametrize the complexity with respect to d, the maximum degree of an element in the tree, as d is usually much smaller than w in trees. For example, in complete binary trees, d = Θ(1), w = Θ(n). The previous known upper bounds are O(dn log² n) [Wang and Honorio, 2019] and O(d² n log n) [Ramtin Afshar et al., 2020], and a recent paper proves a lower bound of Ω(dn log_d n) [Paul Bastide, 2023] for any Las Vegas randomized algorithm. In this paper, we settle the complexity of the problem by presenting a randomized algorithm with worst-case expected O(dnlog_d n) query and time complexity.

Cite as

Jishnu Roychoudhury and Jatin Yadav. An Optimal Algorithm for Sorting in Trees. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{roychoudhury_et_al:LIPIcs.FSTTCS.2023.7,
  author =	{Roychoudhury, Jishnu and Yadav, Jatin},
  title =	{{An Optimal Algorithm for Sorting in Trees}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.7},
  URN =		{urn:nbn:de:0030-drops-193807},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.7},
  annote =	{Keywords: Sorting, Trees}
}

Search Results

Documents authored by Yadav, Jatin

FPT Approximation for Capacitated Sum of Radii

Abstract

Cite as

An Optimal Algorithm for Sorting in Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message